package com.mojito.learn.algorithm.leetcode;

import com.mojito.learn.algorithm.datastructure.TreeNode;

/**
 * @author liufengqiang
 * @date 2021-03-04 17:33:15
 */
public class LeetCode7 {

    /**
     * 700. 二叉搜索树中的搜索
     */
    public TreeNode searchBST(int type, TreeNode root, int val) {
        switch (type) {
            case 1:
                return searchBST1(root, val);
            case 2:
                return searchBST2(root, val);
            default:
                throw new RuntimeException();
        }
    }

    /**
     * 解法一：递归
     * 时间复杂度：O(H)，H 是树的高度，平均时间复杂度是 O(log N)，最坏时间复杂度是 O(N)
     * 空间复杂度：和时间复杂度相同，栈深度消耗
     */
    private TreeNode searchBST1(TreeNode root, int val) {
        if (root == null || val == root.val) {
            return root;
        }

        return searchBST1(root.val > val ? root.left : root.right, val);
    }

    /**
     * 解法二：迭代
     * 时间复杂度：与方法一相同
     * 空间复杂度：O(1)
     */
    private TreeNode searchBST2(TreeNode root, int val) {
        if (root != null && val != root.val) {
            root = root.val > val ? root.left : root.right;
        }
        return root;
    }

    /**
     * 746. 使用最小花费爬楼梯
     */
    public int minCostClimbingStairs(int type, int[] cost) {
        switch (type) {
            case 1:
                return minCostClimbingStairs1(cost);
            case 2:
                return minCostClimbingStairs2(cost);
            default:
                throw new RuntimeException();
        }
    }

    /**
     * 动态规划：dp 为到达下标楼层的最低花费
     * 时间复杂度：O(n) 空间复杂度：O(n)
     */
    private int minCostClimbingStairs1(int[] cost) {
        int[] dp = new int[cost.length + 1];
        dp[0] = 0;
        dp[1] = 0;
        dp[2] = Math.min(cost[0], cost[1]);

        for (int i = 3; i < cost.length + 1; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[cost.length];
    }

    /**
     * 优化空间：使用滚动数组降低空间复杂度
     * 时间复杂度：O(n) 空间复杂度：O(1)
     */
    private int minCostClimbingStairs2(int[] cost) {
        int prev = 0, curr = 0;
        for (int i = 2; i < cost.length + 1; i++) {
            int next = Math.min(curr + cost[i - 1], prev + cost[i - 2]);
            prev = curr;
            curr = next;
        }
        return curr;
    }
}
